package com.leetcode.algorithm.y19.m02;

import java.util.Stack;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * (done)234. 回文链表
 * (done)148. 排序链表
 * (done)24. 两两交换链表中的节点
 * (done)147. 对链表进行插入排序
 * (done)328. 奇偶链表
 * 
 * @author: jie.deng
 * @time: 2019年2月21日 上午11:26:29
 */
public class MySolution0221 {
	
	/**
	 * 234. 回文链表
	 * 
     * 请判断一个链表是否为回文链表。
     * 
     * 示例 1:
     * 
     * 输入: 1->2
     * 输出: false
     * 示例 2:
     * 
     * 输入: 1->2->2->1
     * 输出: true
     * 进阶：
     * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
	 * @param head
	 * @return
	 */
	public boolean isPalindrome(ListNode head) {
		if (head == null) {
			return true;
		}
		ListNode cur = head;
		Stack<Integer> stack = new Stack<Integer>();
		while (cur != null) {
			stack.push(cur.val);
			cur = cur.next;
		}

		cur = head;
		while (!stack.isEmpty()) {
			if (stack.pop() != cur.val) {
				return false;
			}
			cur = cur.next;
		}
		return true;
	}
    
    /**
     * 148. 排序链表
     * 
     * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
     * 
     * 示例 1:
     * 
     * 输入: 4->2->1->3
     * 输出: 1->2->3->4
     * 示例 2:
     * 
     * 输入: -1->5->3->4->0
     * 输出: -1->0->3->4->5
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
		ListNode sentinel = new ListNode(-1); // 待排序链表的哨兵节点
		sentinel.next = head;

		ListNode sortedSentinel = new ListNode(-1); // 已排序链表的哨兵节点

		ListNode cur = sentinel.next; // 当前待排序节点
		while (cur != null) {
			ListNode sortTodo = cur;
			ListNode sortedCur = sortedSentinel.next;
			ListNode sortedPrev = sortedSentinel;
			while (sortedCur != null && sortedCur.val < sortTodo.val) {
				sortedPrev = sortedCur;
				sortedCur = sortedCur.next;
			}

			cur = cur.next; // 下一个待排序节点
			
			// 当前节点插入到已排序链表
			sortedPrev.next = sortTodo; 
			sortedPrev.next.next = sortedCur;
		}
		return sortedSentinel.next;
    }
    
    /**
     * 24. 两两交换链表中的节点
     * 
     * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * 
     * 示例:
     * 
     * 给定 1->2->3->4, 你应该返回 2->1->4->3.
     * @param head
     * @return
     */
	public ListNode swapPairs(ListNode head) {
		ListNode headNew = head;
		ListNode first = head;
		ListNode second = first == null ? null : first.next;
		if (second != null) {
			headNew = head.next;
		}
		ListNode prev = null;
		while (first != null && second != null) {
			// 交换first和second
			first.next = second.next;
			second.next = first;
			if (prev != null) {
				prev.next = second;
			}
			prev = first;
			first = prev.next;
			second = first == null ? null : first.next;
		}
		return headNew;
	}
    
    /**
     * 147. 对链表进行插入排序
     * 
     * 对链表进行插入排序。
     * 
     * 
     * 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
     * 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
     * 
     *  
     * 
     * 插入排序算法：
     * 
     * 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
     * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
     * 重复直到所有输入数据插入完为止。
     *  
     * 
     * 示例 1：
     * 
     * 输入: 4->2->1->3
     * 输出: 1->2->3->4
     * 示例 2：
     * 
     * 输入: -1->5->3->4->0
     * 输出: -1->0->3->4->5
     * @param head
     * @return
     */
	public ListNode insertionSortList(ListNode head) {
		ListNode sentinel = new ListNode(-1); // 待排序链表的哨兵节点
		sentinel.next = head;

		ListNode sortedSentinel = new ListNode(-1); // 已排序链表的哨兵节点

		ListNode cur = sentinel.next; // 当前待排序节点
		while (cur != null) {
			ListNode sortTodo = cur;
			ListNode sortedCur = sortedSentinel.next;
			ListNode sortedPrev = sortedSentinel;
			while (sortedCur != null && sortedCur.val < sortTodo.val) {
				sortedPrev = sortedCur;
				sortedCur = sortedCur.next;
			}

			cur = cur.next; // 下一个待排序节点
			
			// 当前节点插入到已排序链表
			sortedPrev.next = sortTodo; 
			sortedPrev.next.next = sortedCur;
		}
		return sortedSentinel.next;
	}
    
    /**
     * 328. 奇偶链表
     * 
     * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
     * 
     * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
     * 
     * 示例 1:
     * 
     * 输入: 1->2->3->4->5->NULL
     * 输出: 1->3->5->2->4->NULL
     * 示例 2:
     * 
     * 输入: 2->1->3->5->6->4->7->NULL 
     * 输出: 2->3->6->7->1->5->4->NULL
     * 说明:
     * 
     * 应当保持奇数节点和偶数节点的相对顺序。
     * 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
     * @param head
     * @return
     */
	public ListNode oddEvenList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		// 偶数链表
		ListNode evenHead = null;
		ListNode evenTail = null;
		// 目标链表
		ListNode tail = head; // 指向奇数节点
		ListNode cur = head.next; // 指向偶数节点
		while (cur != null) {
			// cur为偶数节点，从原链表移除，并加入到偶数链表
			if (cur != null) {
				// 加入到偶数链表
				if (evenHead == null) {
					evenHead = cur;
					evenTail = evenHead;
				} else {
					evenTail.next = cur;
					evenTail = evenTail.next;
				}

				// 从原链表移除
				tail.next = cur.next;

				// 开始下一轮循环
				if (cur.next != null) {
					tail = cur.next;
					cur = cur.next.next;
				} else {
					break;
				}
			}
		}
		// 偶数链表加入到链表的表尾
		tail.next = evenHead;
		evenTail.next = null;
		return head;
	}
}
